package com.explorati.LeetCode215.Kthlargestelementinanarray;

import java.util.HashSet;
import java.util.Set;

/**
 * 215. Kth Largest Element in an Array 在一个整数序列中查找第k大的元素
 * 
 * Find the kth largest element in an unsorted array. Note that it is the kth
 * largest element in the sorted order, not the kth distinct element.
 * 
 * Input: [3,2,1,5,6,4] and k = 2 Output: 5
 * 
 * Input: [3,2,3,1,2,4,5,5,6] and k = 4 Output: 4
 * 
 * @author explorati
 *
 */
public class Solution {
	public static int findKthLargest(int[] nums, int k) {

		int pos = 0;
		int p = partition(nums, 0, nums.length - 1);
		while ((pos = nums.length - p) != k) {

			if (pos > k) {
				p = partition(nums, p + 1, nums.length - 1);
			} else {
				p = partition(nums, 0, p - 1);
			}
		}
		return nums[p];
	}

	// 利用快排返回元素位置(位置即Kth)
	public static int partition(int[] nums, int l, int r) {
		swap(nums, l, (int) (Math.random() * (r - l + 1) + l));
		int p = nums[l];
		
		int lt = l;
		int i = l + 1;
		while (i <= r) {
			if (nums[i] <= p) {
				swap(nums, ++lt, i++);
			} else {
				i++;
			}
		}
		swap(nums, lt, l);
		return lt;
	}

	public static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}

	public static void main(String[] args) {
		int[] arr = { 3,2,3,1,2,4,5,5,6 };
		int i = findKthLargest(arr, 5);
		System.out.println(i);
	}
}
// 查找第k在排序后的数组中的位置
// lt指向第一个小于k的元素的位置，gt指向第一个大于k的位置
// int lt = -1, gt = nums.length;
// int i = 0;
// while (i < gt) {
// if (nums[i] < k) {
// swap(nums, ++lt, i++);
// } else if (nums[i] > k) {
// swap(nums, --gt, i);
// } else {
// i++;
// }
// }
//
// return nums.length - gt + 1;
